package Hot_100;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Description 31. 下一个排列
 * @Author Firenut
 * @Date 2023-05-02 16点40分
 * 参考：https://leetcode.cn/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
 */
public class T31_nextPermutation {
    @Test
    public void test() {
        int nums[] = {3,2,1};
        nextPermutation(nums);
//        for (int i = 0; i < nums.length; i++) {
//            System.out.print(nums[i]+" ");
//        }
    }

    // 1 2 3 8 5 7 6 4
    // 思路: 从后往前,找到升序的 两个数字 i,j
    // [j,end]的数字必然是降序,在[j,end]之间,
    // 按照从后往前找第一个大于nums[i]的数字nums[k] (为了让数字的增大幅度最小)
    // 交换nums[i]和nums[k],此时[j,end]依旧是降序的,直接将其反转
    // 最终得到的就是下一个排列
    public void nextPermutation(int[] nums) {
        // 从后往前,找到升序的 两个数字 i,j (i<j)
        int i=0,j=nums.length-1;
        // i需要先初始化,如果一开始数字为123,那么i就不会被赋值,后面使用nums[i]必然有问题
        while(j>0){
            if(nums[j]>nums[j-1]){
                i=j-1;
                break;
            }
            j--;
        }
        // 从后往前找第一个大于nums[i]的数字nums[k] 并交换
        int k;
        for(k=nums.length-1;k>=j;k--){
            if(nums[k]>nums[i]){
                swap(i,k,nums);
                break;
            }
        }
        // 反转[j,end]之间的元素
        int end = nums.length-1;
        while(j<end){
            swap(j,end,nums);
            j++;
            end--;
        }
    }

    void swap(int i,int j,int []nums){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}